package com.chj.jz.dp.class01;

//https://www.lintcode.com/problem/coin-change/description
public class Code01_CoinChang {
	public static int coinChang(int[] A, int M) {
		int n = A.length;
		int[] f = new int[M + 1];

		f[0] = 0;
		int i, k;
		for (i = 1; i <= M; i++) {
			f[i] = Integer.MAX_VALUE;
			for (k = 0; k < n; k++) {
				if (i >= A[k] && f[i - A[k]] != Integer.MAX_VALUE) {
					f[i] = Math.min(f[i], f[i - A[k]] + 1);
				}
			}
			System.out.println("f["+i+"]="+f[i]);
		}

		if (f[M] == Integer.MAX_VALUE) {
			return -1;
		} else {
			return f[M];
		}
	}

	public static void main(String[] args) {
		{
			int[] arr = new int[] { 1, 2, 5 };
			int M = 11;
			System.out.println(coinChang(arr, M));
		}
		{
			int[] arr = new int[] { 2, 5,7 };
			int M = 27;
			System.out.println(coinChang(arr, M));
		}
		{
			int[] arr = new int[] { 2 };
			int M = 3;
			System.out.println(coinChang(arr, M));
		}
	}
}
